package com.dzsw.datastruct.tree.binary;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

public class RecursionBinaryTreeImpl<E> extends AbstractBinaryTreeImpl<E> {

    private static Logger logger = LogManager.getLogger(RecursionBinaryTreeImpl.class);

    @Override
    public void preOrder(Visitor<E> visitor) {
        if (this.root == null) {
            throw new RuntimeException("root is null.");
        }
        preOrder(this.root, visitor);
    }

    /**
     * 前序遍历（递归），根、左、右
     * @param node
     * @param visitor
     */
    private void preOrder(Node<E> node, Visitor<E> visitor) {
        //
        if (visitor.isStop()) {
            return;
        }
        visitor.setStop(visitor.visit(node.getElement()));
        preOrder(node.getLeft(), visitor);
        preOrder(node.getRight(), visitor);
    }

    @Override
    public void inOrder(Visitor<E> visitor) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        inOrder(this.root, visitor);
    }

    /**
     * 中序遍历（递归），左、根、右
     * @param node
     * @param visitor
     */
    private void inOrder(Node<E> node, Visitor<E> visitor) {
        inOrder(node.getLeft(), visitor);
        //
        if (visitor.isStop()) {
            return;
        }
        visitor.setStop(visitor.visit(node.getElement()));
        inOrder(node.getRight(), visitor);
    }

    @Override
    public void postOrder(Visitor<E> visitor) {
        if (root == null) {
            throw new RuntimeException("root is null.");
        }
        postOrder(this.root, visitor);
    }

    /**
     * 后序遍历（递归），左、右、根
     * @param node
     * @param visitor
     */
    private void postOrder(Node<E> node, Visitor<E> visitor) {
        preOrder(node.getLeft(), visitor);
        preOrder(node.getRight(), visitor);
        //
        if (visitor.isStop()) {
            return;
        }
        visitor.setStop(visitor.visit(node.getElement()));
    }

    @Override
    public int height() {
        return height(this.root);
    }

    /**
     * (递归法)获取传入节点的高度
     * @param node
     * @return
     */
    private int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.getLeft()), height(node.getRight()));
    }
}
